package two.prefixSum_difference;

/**
 * 最大子序和
 */
public class MaxSubArray {

    //时间复杂度：O(n)
    //思路：前缀和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] S = new int[n + 1]; //nums的前缀和
        for(int i = 1; i <= n; i++){
            S[i] = S[i - 1] + nums[i - 1];
        }
        int[] pre = new int[n + 1];//nums的前缀和最小值
        for(int i = 1; i <= n; i++){
            pre[i] = Math.min(pre[i - 1], S[i]);
        }
        int answer = Integer.MIN_VALUE;//注意点：默认值不能为0
        for(int i = 1; i <= n; i++){
            answer = Math.max(answer, S[i] - pre[i - 1]); //找到最大子序和
        }
        return answer;
    }
}
